1. Field of the Invention
The present invention relates to a cache subsystem in a data processing system that resolves conflicts which may arise due to the interaction of central processing unit (CPU) read transactions, CPU write transactions, and line-fill transactions in a two (2) level non-blocking cache system. Due to the non-blocking nature of such caches more than one such transaction can be in progress at the same time. This can give rise to read-miss/write-miss and read-miss/read-miss conflicts.
More particularly, when a CPU write transaction is initiated shortly before or after a CPU read transaction, both can be active in the cache subsystem at the same time. If both transactions miss the level one (L1) cache and hit the level (L2) cache, and each of them uses the same line in memory, it is possible for the following sequence of events to occur. First, the CPU read transaction is initially processed by the L1 cache and since the read misses the L1, an L1 line-fill operation is initiated to transfer a line of data from the L2 cache to the L1 cache. Second, the CPU write transaction is then processed by the L1 cache, and since the line of data (same as that for the previous read) in which it resides is still not in the L1 cache, it misses the L1 cache and is passed on to the L2 cache. Third, the L1 line-fill transaction (generated by the L1 read-miss) places the requested line from the L2 cache into the L1 cache. Fourth, the write transaction then updates the addressed line in the L2 cache, after the old version of that same line has been placed in the L1 cache by the previous L1 line-fill.
It can be seen that this scenario would result in the line in the L1 cache not being updated with data from the most recent write transaction, such that if data from that line was later requested from the L1 cache via a CPU read transaction it would result in stale data being returned to the CPU.
Further, when a CPU read transaction is initiated shortly before or after another CPU read transaction, both can be active in the cache system at the same time. If both transactions miss the L1 cache and hit the L2 cache, and each of them uses the same memory address, then they will both generate an L1 line-fill transaction that attempts to load the same line from the L2 cache into the L1 cache. This can cause harmful effects if the L1 cache is a multi-way cache, which would allow the same line to be loaded into two different locations in the L1 cache, giving rise to coherency problems if the CPU later attempts to modify that line via a CPU write cycle. Since the L1 cache is normally incapable of modifying two copies of the same line simultaneously, one copy would end up containing stale data that could be returned to the CPU on a subsequent CPU read.
2. Description of Related Art
Conventional systems do not address the problems described herein in the same manner. Other systems typically use explicit conflict detection techniques, such as the addition of comparators to determine when read/write (R/W) transactions are attempting to use the same address in the memory system (caches and/or main memory).
For CPU write transactions in a typical cache system, the L1 cache is only accessed before the L2 cache, not after. If the L1 cache is hit then there is no problem, but if the transaction misses the L1 cache then there is the possibility of an L1 read-miss/write-miss conflict, as described above. To avoid this, the address of each new CPU write transaction is explicitly checked (compared) against the address of any L1 line-fill transaction (caused by the L1 read-miss) in progress to ensure that there is no conflict before allowing the write-transaction to proceed. If there is a conflict, then the CPU write transaction is stalled until the L1 line-fill is completed and the conflict thus resolved.
Similarly, to avoid L1 read-miss/read-miss conflicts in conventional systems, the address of each new CPU read transaction is explicitly checked (compared) against the address of any L1 line-fill transaction (caused by a previous L1 read-miss) in progress to ensure that it does not conflict before allowing the read transaction to proceed. If it does conflict, then the CPU read transaction is either stalled until the line-fill is completed and the conflict thus resolved (the second CPU read will then get an L1 hit when allowed to proceed), or is marked as invalid so that it will not generate another L1 line-fill.
Therefore, it can be seen that a need exists for a data processing system having a cache subsystem (CSS) that is structured to avoid collisions between read/write transactions issued by the central processing unit independent of the order, or sequence in which they are issued. Further, a system that provides the previously described functions without the need for additional complexity, such as comparator circuits, or other logic would be highly desirable.
In contrast to the prior art, the present invention provides a five (5) stage memory access transaction pipeline which sequentially places the L1 cache after the L2 cache.
Broadly, the present invention is a cache subsystem in a data processing system structured to place the L1 cache RAMs after the L2 cache RAMs in the pipeline for processing both CPU write transactions and L1 line-fill transactions. In this manner it is naturally guaranteed that lines loaded into the L1 cache are updated by all CPU write transactions without having to perform any explicit checks. The present invention also places the L1 tag RAM before the L1 data RAM for both CPU write transactions and L1 line-fill transactions, such that CPU write transactions may check that a line is in the L1 cache before updating it, and L1 line-fill transactions may check that the line to be transferred from the L2 cache to the L1 cache is not already in the L1 cache.